package primary.primary0;

public class S0153乘积最大子数组 {

    /**
     * 答案，
     */
    public int maxProduct2(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            // 当前点最大值为 前一个节点最大值 * 当前节点，前一个节点最小值 * 当前节点，当前节点
            // 只会是三种情况之一。并且不用考虑正负以及0，因为已经在这个情况里了。秒。当前点最小值亦然。
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }


    /**
     * 66, 43
     * 大概就是动态规划，关键是0值比较麻烦
     */
    public int maxProduct(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int maxMultiplyRes = nums[0];
        int[] preRes = new int[]{0, 0};
        int[] curRes = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                curRes[0] = Math.max(nums[i], preRes[0] * nums[i]);
                curRes[1] = Math.min(nums[i], preRes[1] * nums[i]);
            } else if (nums[i] < 0) {
                curRes[0] = Math.max(nums[i], preRes[1] * nums[i]);
                curRes[1] = Math.min(nums[i], preRes[0] * nums[i]);
            } else {
                // 当前值为0
                curRes[0] = 0;
                curRes[1] = 0;
            }
            maxMultiplyRes = Math.max(maxMultiplyRes, curRes[0]);
            // preRes = curRes;这样写会导致两个指针指向同一个对象，
            // 比如当前[2, -2] nums[i] -2, 第一步 变成[4, -2]，第二步[4, -8]，第二步的时候用了第一步的结果。
            // 一定要小心这种值传递，搞不清楚的话可以用四个变量来做，防止这种情况。
            preRes[0] = curRes[0];
            preRes[1] = curRes[1];
        }
        return maxMultiplyRes;
    }
}
